/*
 * @lc app=leetcode.cn id=707 lang=javascript
 *
 * [707] 设计链表
 */
// @lc code=start
function Link(val = null) {
  this.val = val
  this.next = null
  this.prev = null
}

// 提供两个虚拟头尾节点
// 提供长度信息
var MyLinkedList = function() {
  this.size = 0
  this.head = new Link()
  this.tail = new Link()
  this.head.next = this.tail
  this.tail.prev = this.head
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
  if (index < 0 || index >= this.size) return -1
  let current = this.head
  if (index + 1 < this.size - index) {
    for (let i = 0; i < index + 1; i++) {
      current = current.next
    }
  } else {
    current = this.tail
    for (let i = 0; i < this.size - index; i++) {
      current = current.prev
    }
  }
  return current.val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
  let prev = this.head
  let prevNext = prev.next
  let newLink = new Link(val)
  
  prev.next = newLink
  newLink.prev = prev
  newLink.next = prevNext
  prevNext.prev = newLink
  this.size ++
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
  let tail = this.tail
  let tailPrev = tail.prev
  let newLink = new Link(val)
  
  tailPrev.next = newLink
  newLink.prev = tailPrev
  newLink.next = tail
  tail.prev = newLink
  this.size ++
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this.size) return
  if (index < 0) index = 0

  let prev, succ;
  if (index < this.size - index) {
    prev = this.head
    for (let i = 0; i < index; i++) {
      prev = prev.next
    }
    succ = prev.next
  } else {
    succ = this.tail
    for (let i = 0; i < this.size - index; i++) {
      succ = succ.prev
    }
    prev = succ.prev
  }
  let newLink = new Link(val)
  prev.next = newLink
  succ.prev = newLink
  newLink.next = succ
  newLink.prev = prev

  this.size ++
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
  if (index < 0 || index >= this.size) return

  let current = this.head
  if (index + 1 < this.size - index) {
    for (let i = 0; i < index + 1; i++) {
      current = current.next
    }
  } else {
    current = this.tail
    for (let i = 0; i < this.size - index; i++) {
      current = current.prev
    }
  }

  current.prev.next = current.next
  current.next.prev = current.prev

  this.size--
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */
// @lc code=end

